package xiaomin.demo.algorithm;

public class Lesson13 {
    /*
    分区函数的目的就是不断的逼近自己需要的值
    不断逼近start 和 end，找到index刚好等于start
     */
    public static void run(){
//        int[] arr={11,3,6,4,7,3,5,8,9,3,4,6,8,9,10,22,33,56,1,44,767,34,356,432};
        int[] arr={1,2,3,4,5,6,7,8,9,10,11,12,13,14};
        int[] result={0};
        int k=5;
        int index=-1;
        int start=0,end=arr.length-1;
        while (index!=start){
            result[0]=0;
            index=getIndex(arr,start,end,result);
            if(k>=result[0] ){//每次找到新的index都跟k比较大小
                k=k-result[0];
                start=index+1;//当start不往前走了,则说明找到了
            }
            else if(k<result[0] && index!=start){
                end=index-1;
            }
        }

        for(int x:arr) {
            System.out.println(x);
        }
        System.out.println(start);

    }

    public static int getIndex(int[] arr,int start,int end,int[] result){
        //第一个数字
        int tmp=arr[start];
        int startPointer=start;
        int endPointer=end;
        //双向区间扫描
        while (startPointer<endPointer){
            //先从end扫描
            while (startPointer<endPointer && arr[endPointer]>=tmp){
                endPointer--;
            }
            //遇到小的,填坑到左边
            arr[startPointer]=arr[endPointer];
            //从start扫描
            while(startPointer<endPointer && arr[startPointer]<=tmp){

//                System.out.println(result[0]);
                startPointer++;
            }
            //遇到大的,填坑到右边
            arr[endPointer]=arr[startPointer];
        }

        int i=start;
        while (i<=startPointer){
            result[0]=result[0]+arr[i];
            i++;
        }

        arr[startPointer]=tmp;

        return startPointer;
    }
}
